class Node(object):
    def __init__(self,elem=-1,left=None,right=None):
        self.elem = elem
        self.left = left
        self.right = right



class Tree(object):
    def __init__(self):
        self.root =None
        self.queue = []

    def insert_node(self,elem):
        new_node = Node(elem)
        self.queue.append(new_node)
        if self.root is None:
            self.root = new_node
        elif self.queue[0].left is None :
            self.queue[0].left = new_node
        else :
            self.queue[0].right = new_node
            self.queue.pop(0)

    def pre_order(self,root):    #非递归先序遍历
        if root is None:
            return
        stack = []
        node = root
        while node or stack:
            while node:
                print(node.elem, end='')
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right

    def mid_order(self,root):
        if root is None:
            return
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            print(node.elem, end='')
            node = node.right

    def post_order(self,root):
        if root is None:
            return
        stack1 = []
        stack2 = []
        node = root


if __name__ == '__main__':
    elems = range(10)
    tree = Tree()
    for elem in elems:
        tree.insert_node(elem)
    print("xianxu")
    tree.pre_order(tree.root)
    print("\nzhongxu")
    tree.mid_order(tree.root)


